/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "atomic.h"
#include "map.h"

using namespace nbds;

map_base::map_base() : root((elem*)0) { }

map_base::map_base(const map_base &x, void *(*ck)(void*), void *(*cv)(void*)) :
	cpy_kp(ck), cpy_vp(cv) {
	cpy_elem_r(&root, x.root);
}

map_base::~map_base() {
	del_elem_r(root);
}

void map_base::cpy_elem_r(elem **dst, elem *src) {
	if (src == (elem*)0) {
		*dst = 0;
		return;
	}

	elem *e = new elem;
	e->key = cpy_kp(src->key);
	e->value = cpy_vp(src->value);
	cpy_elem_r(&e->lesser, src->lesser);
	cpy_elem_r(&e->greater, src->greater);

	*dst = e;
}

void map_base::del_elem_r(elem *e) {
	if (e == (elem*)0)
		return;

	del_kp(e->key);
	del_vp(e->value);
	del_elem_r(e->lesser);
	del_elem_r(e->greater);

	delete e;
}

bool map_base::nul_elem_r(elem *e) {
	if (e == (elem*)0)
		return true;

	return e->value == (void*)0 &&
		nul_elem_r(e->greater) &&
		nul_elem_r(e->lesser);
}

void *map_base::get_(const void *key) const {
	elem *current = root;
	while (current != NULL) {
		if (cmp_eq(current->key, key))
			return arch::get(&current->value);
		else if (cmp_l(current->key, key))
			current = arch::get(&current->greater);
		else
			current = arch::get(&current->lesser);
	}

	return NULL;
}

void map_base::set_(void *key, void *value) {
	elem *x = new elem;
	x->key = key;
	x->value = value;
	x->lesser = NULL;
	x->greater = NULL;

	while (!try_add(x, true));
}

void map_base::add_(void *key, void *value) {
	elem *x = new elem;
	x->key = key;
	x->value = value;
	x->lesser = NULL;
	x->greater = NULL;

	while (!try_add(x, false));
}

bool map_base::try_add(elem *x, bool replace) {
	elem *current = arch::get(&root);
	while (current != NULL) {
		if (cmp_eq(current->key, x->key)) {
			if (!replace)
				arch::cmp_and_swp(&current->value, (void*)0, x->value);
			else
				arch::xchg(&current->value, x->value);
			return true;
		} else if (cmp_l(current->key, x->key)) {
			if (arch::cmp_and_swp(&current->greater, (elem*)0, x) == 0)
				return true;

			elem *child = arch::get(&current->greater);

			if (cmp_g(child->key, x->key)) {
				x->greater = child;
				return arch::cmp_and_swp(&current->greater, child, x) == child;
			} else
				current = arch::get(&current->greater);
		} else {
			if (arch::cmp_and_swp(&current->lesser, (elem*)0, x) == 0)
				return true;

			elem *child = arch::get(&current->lesser);

			if (cmp_l(child->key, x->key)) {
				x->lesser = child;
				return arch::cmp_and_swp(&current->lesser, child, x) == child;
			} else
				current = arch::get(&current->lesser);
		}
	}

	return arch::cmp_and_swp(&root, (elem*)0, x) == NULL;
}

void *map_base::remove_(const void *key) {
	elem *current = arch::get(&root);
	while (current != NULL) {
		if (cmp_eq(current->key, key)) {
			void *val = arch::xchg(&current->value, (void*)0);
			return val;
		} else if (cmp_l(current->key, key))
			current = arch::get(&current->greater);
		else
			current = arch::get(&current->lesser);
	}

	return NULL;
}

bool map_base::is_empty_() {
	return nul_elem_r(root);
}
